class Solution {
    /**
        完全背包-未优化版本
    **/
    public int change(int amount, int[] coins) {
        int len = coins.length;
        int[][] d = new int[len+1][amount+1];
        d[0][0] = 1;
        for (int i = 1; i <= len; i++) {
            int val = coins[i-1];
            for (int money = 0; money <= amount; money++) {
                d[i][money] = d[i-1][money];
                // 这个循环就是和01背包的不同，完全背包每个物品可以装无限次
                for (int count = 1; count*val <= money; count++) {
                    d[i][money] += d[i-1][ money- count*val ];
                }
            }
        }
        return d[len][amount];
    }
}
class Solution {
    /**
        完全背包-优化数组版本

        注意和背包模板题不同的是 d[i]表示的不是容量为i能装的value 
        而是容量为i时 能装的物品组合数
     */
    public int change(int amount, int[] coins) {
        int len = coins.length;
        int[] d = new int[amount+1];
        d[0] = 1;
        for(int i=0; i<len; i++){
            for(int w=0; w<=amount; w++){
                if( w-coins[i]>=0 ){
                    /* 
                    如果是完全背包 那么这里应该是 
                    d[w] = Math.max(d[w], d[w-coins[i]+coins[i]) 同时d[0]=0
                    */
                    d[ w ] += d[ w-coins[i] ];
                }
            }
            // System.out.println(Arrays.toString(d));
        }
        
        return d[amount];
    }
}